import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

public class Heap<T> {

	private ArrayList<T> heap;
	private HashMap<T, Integer> indexMap;
	private int heapSize;
	private Comparator<? super T> comparator;

	public Heap(Comparator<? super T> com) {
		heap = new ArrayList<>();
		indexMap = new HashMap<>();
		heapSize = 0;
		comparator = com;
	}

	public boolean isEmpty() {
		return heapSize == 0;
	}

	public int size() {
		return heapSize;
	}

	public void push(T value) {
		heap.add(value);
		indexMap.put(value, heapSize);
		heapInsert(heapSize++);
	}
	/**
	 * 告知我，这个value内部的数据被改了，我要调整结构，重新构成小根堆
	 * 但是我并不知道这个数是变大了还是变小了，但是我要么向上调整，
	 * 要么向下调整，两个逻辑只会命中一个。
	 * @param value
	 */
	public void resign(T value) {
		int index = indexMap.get(value);
		heapInsert(index);
		heapify(index);
	}

	private void swap(int a, int b) {
		T o1 = heap.get(a);
		T o2 = heap.get(b);
		heap.set(a, o2);
		heap.set(b, o1);
		indexMap.put(o1, b);
		indexMap.put(o2, a);
	}

	public T pop() {
		T ret = heap.get(0);
		swap(0, --heapSize);
		heap.remove(heapSize);
		indexMap.remove(ret);
		heapify(0);
		return ret;
	}

	/**
	 * comparator：arg0 < arg1 返回负数，while成立条件，index位置的数小于父亲节点数
	 *
	 * @param index
	 */
	private void heapInsert(int index) {
		while (comparator.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
			swap(index, (index - 1) / 2);
			index = (index - 1) / 2;
		}
	}

	private void heapify(int index) {
		int left = index * 2 + 1;
		while (left < heapSize) {
			int largest = left + 1 < heapSize && comparator.compare(heap.get(left + 1), heap.get(left)) < 0
					? left + 1 : left;
			largest = comparator.compare(heap.get(index), heap.get(largest)) < 0 ? index : largest;
			if (largest == index) {
				return;
			}
			swap(largest, index);
			index = largest;
			left = index * 2 + 1;
		}
	}

}
